import sun.reflect.generics.tree.Tree;

import javax.swing.tree.TreeNode;
import java.util.*;

public class Test {

     //Definition for a binary tree node.
    public class TreeNode {
       int val;
       TreeNode left;
        TreeNode right;
        TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
           this.left = left;
          this.right = right;
          }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>>list=new ArrayList<>();
        if(root==null){
            return list;
        }
        Queue<TreeNode>qu=new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
            int size=qu.size();
            List<Integer>tmp=new ArrayList<>();
            while(size>0){
                TreeNode cur=qu.poll();
                size--;
                tmp.add(cur.val);
                if(cur.left!=null){
                    qu.offer(cur.left);
                }
                if(cur.right!=null){
                    qu.offer(cur.right);
                }
                list.add(tmp);
            }
        }
        return list;
    }
    public void inorder(TreeNode root){
        if(root==null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    public int i=0;
    public   TreeNode createTree(String str){
        TreeNode root=null;
        if(str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree(str);
            root.right=createTree(str);
        }else{
            i++;
        }
        return root;
    }
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root==null||p==null||q==null){
                return null;
            }
            Stack<TreeNode>stack1=new Stack<>();
            getPath(root,p,stack1);
            Stack<TreeNode>stack2=new Stack<>();
            getPath(root,q,stack2);
            int size1=stack1.size();
            int size2=stack2.size();
            if(size1>size2){
                int size=size1-size2;
                while(size>0){
                    stack1.pop();
                    size--;
                }
            }else{
                int size=size2-size1;
                while(size>0){
                    stack2.pop();
                    size--;
                }
            }
           while(stack1.peek()!=stack2.peek()){
               stack1.pop();
               stack2.pop();
           }

            return stack1.peek();
        }
        private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode>stack){
            if(root==null||node==null){
                return false;
            }
            stack.push(root);

            if(root==node){
                return true;
            }
            boolean flg1=getPath(root.left,node,stack);
            if(flg1==true){
                return true;
            }
            boolean flg2=getPath(root.right,node,stack);
            if(flg2==true){
                return true;
            }
            stack.pop();
            return false;
        }
    }
    class Solution1{
        public TreeNode lowestCommonAncestor1(TreeNode root,TreeNode p,TreeNode q){
            if(root==null){
                return null;
            }
            if(root==p||root==q){
                return root;
            }
            TreeNode ret1=lowestCommonAncestor1(root.left,p,q);
            TreeNode ret2=lowestCommonAncestor1(root.right,p,q);
            if(ret1!=null&&ret2!=null){
                return root;
            } else if (ret1!=null) {
                return ret1;
            }else {
                return ret2;
            }
        }
    }
}
